package com.algorithm.threehundred2fourhundred;

import java.util.*;

/**
 * @author: tzj
 * @create: 2021-06-02
 **/
public class Intersect_350 {

    public static void main(String[] args) {
//        int[] nums1 = {1, 2, 2, 1}, nums2 = {2, 2};
//        int[] nums1 = {4, 9, 5}, nums2 = {9, 4, 9, 8, 4};
        int[] nums1 = {1, 2}, nums2 = {1, 1};
        System.out.println(Arrays.toString(intersect(nums1, nums2)));
    }

    public static int[] intersect(int[] nums1, int[] nums2) {
        if (nums1.length > nums2.length) {
            return intersect(nums2, nums1);
        }
        // 初始化,默认先把nums1的数据放进map，把数据少的放进去，减少空间复杂度
        Map<Integer, Integer> init = new HashMap<>(16);
        for (int num : nums1) {
            int count = init.getOrDefault(num, 0) + 1;
            init.put(num, count);
        }

        int[] intersection = new int[nums1.length];
        int index = 0;
        for (int num : nums2) {
            // 第一次获取每个值的存储次数，大于零的话就是结果需要的，然后次数减一，再判断是否大于零，
            // 大于的话就把次数减去的值存储进去，否则从hash表中移除
            int count = init.getOrDefault(num, 0);
            if (count > 0) {
                intersection[index++] = num;
                count--;
                if (count > 0) {
                    init.put(num, count);
                } else {
                    init.remove(num);
                }
            }
        }
        // 截取从0到数组指针移动到的位置
        return Arrays.copyOfRange(intersection, 0, index);
    }
}
